package com.zlk.algorithm.algorithm.sort;

import org.junit.Test;

/**
 * @program: algorithm
 * @ClassName RadixSort
 * @description: 基数排序 非负数  负数也可以改   找到最小值 - min  然后所有值加 min ，排完序之后在减min
 * 算法思想：
 *    1、遍历数组找到最大的数max 获取max的最大进位 digit
 *    2、for循环遍历从1进位开始 遍历到 digit
 *    3、digit循环中创建0-9数组count  d表示当前位  遍历数组，获取当前i d位的数 j  count[j] =1重复出现加1
 *              count[0] 当前位(d位)是0的数字有多少个
 *              count[1] 当前位(d位)是(0和1)的数字有多少个
 *              count[2] 当前位(d位)是(0、1和2)的数字有多少个
 *              count[i] 当前位(d位)是(0~i)的数字有多少个
 *              前缀和的意思
 *    4、然后倒叙遍历数组，找到当前i 所属位的值 j 这个j就是当前count[j-1] 的位置 应为从右到左的
 * @author: slfang
 * @create: 2024-01-29 14:04
 * @Version 1.0
 **/
public class RadixSort {

    @Test
    public void test1(){

        //((x / ((int) Math.pow(10, d - 1))) % 10);
        int max = 1293;
        int i = max / 1;
        System.out.println(i % 10);
        System.out.println();
    }

    // only for no-negative value
    public static void radixSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        radixSort(arr, 0, arr.length - 1, maxbits(arr));
    }

    /**
     * 找到最大数 所占得最大十进位数
     * @param arr
     * @return
     */
    public static int maxbits(int[] arr) {
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
        }
        int res = 0;
        while (max != 0) {
            res++;
            max /= 10;
        }
        return res;
    }

    // arr[L..R]排序  ,  最大值的十进制位数digit
    public static void radixSort(int[] arr, int L, int R, int digit) {
        final int radix = 10;
        int i = 0, j = 0;
        // 有多少个数准备多少个辅助空间
        int[] help = new int[R - L + 1];
        for (int d = 1; d <= digit; d++) { // 有多少位就进出几次
            // 10个空间
            // count[0] 当前位(d位)是0的数字有多少个
            // count[1] 当前位(d位)是(0和1)的数字有多少个
            // count[2] 当前位(d位)是(0、1和2)的数字有多少个
            // count[i] 当前位(d位)是(0~i)的数字有多少个
            int[] count = new int[radix]; // count[0..9]
            for (i = L; i <= R; i++) {
                // 103  1   3
                // 209  1   9
                //getDigit 获取当前 d i位置数据 d位上的数
                j = getDigit(arr[i], d);
                count[j]++;
            }
            //获取到前缀和数据
            for (i = 1; i < radix; i++) {
                count[i] = count[i] + count[i - 1];
            }

            for (i = R; i >= L; i--) {
                j = getDigit(arr[i], d);
                help[count[j] - 1] = arr[i];
                count[j]--;
            }
            for (i = L, j = 0; i <= R; i++, j++) {
                arr[i] = help[j];
            }
        }
    }

    public static int getDigit(int x, int d) {
        return ((x / ((int) Math.pow(10, d - 1))) % 10);
    }
}
